package club.xiaojiawei.monotonestack;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 6/12/22 5:13 PM
 * @question 42. 接雨水
 * @description 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 */
public class Trap42 {

    public static void main(String[] args) {
        Trap42 test = new Trap42();
        int result = test.trap2(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1});
        System.out.println(result);
    }

    /**
     * 官方-dp（nb）
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     * @param height
     * @return
     */
    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) {
            return 0;
        }
        int[] leftMax = new int[n];
        leftMax[0] = height[0];
        for (int i = 1; i < n; ++i) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }
        int[] rightMax = new int[n];
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }

    /**
     * 官方-单调栈
     * @param height
     * @return
     */
    public int trap2(int[] height) {
        int ans = 0;
        Deque<Integer> stack = new LinkedList<Integer>();
        int n = height.length;
        for (int i = 0; i < n; ++i) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int top = stack.pop();
                if (stack.isEmpty()) {
                    break;
                }
                int left = stack.peek();
                int currWidth = i - left - 1;
                int currHeight = Math.min(height[left], height[i]) - height[top];
                ans += currWidth * currHeight;
            }
            stack.push(i);
        }
        return ans;
    }

    /**
     * 官方——双指针
     * @param height
     * @return
     */
    public int trap3(int[] height) {
        int sum = 0;
        for (int i = 0; i < height.length; i++) {
            // 第一个柱子和最后一个柱子不接雨水
            if (i==0 || i== height.length - 1) continue;
            int rHeight = height[i]; // 记录右边柱子的最高高度
            int lHeight = height[i]; // 记录左边柱子的最高高度
            for (int r = i+1; r < height.length; r++) {
                if (height[r] > rHeight) rHeight = height[r];
            }
            for (int l = i-1; l >= 0; l--) {
                if(height[l] > lHeight) lHeight = height[l];
            }
            int h = Math.min(lHeight, rHeight) - height[i];
            if (h > 0) sum += h;
        }
        return sum;
    }

    /**
     * 民间——dp（滚动数组）
     * @param height
     * @return
     */
    public int trap4(int[] height) {
        if(height.length<2){
            return 0;
        }
        int l=1;
        int r=height.length-2;
        int maxLeft=0;
        int maxRight=0;
        int result=0;
        while(l<=r){
            if(height[l-1]<height[r+1]){
                maxLeft=Math.max(maxLeft,height[l-1]);
                if(maxLeft>height[l]){
                    result += (maxLeft-height[l]);
                }
                l++;
            }else{
                maxRight=Math.max(maxRight,height[r+1]);
                if(maxRight>height[r]){
                    result+=(maxRight-height[r]);
                }
                r--;
            }
        }
        return result;
    }
}
